package org.example.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @version 1.0.0
 * @author: lynn
 * @description: 给你一个链表数组，每个链表都已经按升序排列 ,请你将所有链表合并到一个升序链表中，返回合并后的链表
 * @date: 2021/7/24 13:07
 */
public class LC23 {
    public static void main(String[] args) {

    }
    //暴力解法，先收集所有的val，然后val排序，再然后尾插法填充链表
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummyNode=new ListNode(0);
        ListNode tail=dummyNode;
        List<Integer> valList=new ArrayList<>();
        for (int i = 0; i <lists.length ; i++) { //时间复杂度是O(n)
            while (lists[i]!=null) {
                valList.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        Collections.sort(valList);  // O(NlogN)
        //构建一个list，尾插法
        for (int i = 0; i <valList.size() ; i++) {//O(n)
            ListNode newNode=new ListNode(valList.get(i));
            tail.next=newNode;
            tail=newNode;
        }
        return  dummyNode.next;
    }

    //非暴力解法 https://www.bilibili.com/video/BV1NK4y1Y722?from=search&seid=1572763717196840234
    public ListNode mergeKListsPrioryQueue(ListNode[] lists) {
        //fixme 用一个最小的优先队列
        PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>(((o1, o2) -> {
            return o1.val-o2.val;
        }));
        ListNode dummyNode=new ListNode(0);
        ListNode tail=dummyNode;
        for (ListNode head:lists){
            while (head!=null){
                priorityQueue.offer(head);
                head=head.next;
            }
        }

        while (priorityQueue.size()>0){
            tail.next=priorityQueue.poll();
            tail=tail.next;
        }
        return dummyNode.next;
    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


}
